/**
 * Dijkstra.java
 *
 * @author Hagen Boehm
 */


package SSF.OS.OSPFv2;


import java.util.*;


// ======================== class SSF.OS.OSPFv2.Dijkstra ===================== //
/**
 * Dijkstra's shortest path algorithm.  Most of the algorithm is taken from
 * <i>Introduction to Algorithms</i> by Cormen, Leiserson and Rivest.
 */
public class Dijkstra {

  // ......................... constants ........................... //

  // ........................ member data .......................... //

  /** An mapping of vertices in the graph upon which Dijkstra's algorithm is
   *  being run. */
  private HashMap vertices;

  /** A mapping to be used as a priority queue of vertices by distance. */
  private HashMap candidates;

  /** A boolean value indicating transit capability of the area in which this Dijkstra
   *  is used.
   */
  private boolean isTransitCapable;

  /** A HashMap representing all vertices which have been inserted in the shortest-path-tree */
  private HashMap spTree;

  /** The vertex which was just added to the spTree. */
  private Vertex justAdded;

  /** The vertex representing the root of the spTree. */
  private Vertex root;

  /** A link to the OSPF session. */
  private OSPF myOSPF;

  /** A link to the associated area. */
  private AreaData myArea;


  // -------------------------- constructor Dijkstra ----------------------- //
  /**
   * Construct a new instance of Dijkstra's algorithm. Build the vertices
   * participating in calculation.
   * @param lsas A Vector holding all LSAs stored in the LS Database.
   * @param o A reference to the OSPF session this Dijkstra belogs to.
   * @param myArea A reference to the area this Dijkstra belongs to.  
   */
  public Dijkstra(Vector lsas, OSPF o, AreaData myArea) {
    myOSPF = o;
    this.myArea = myArea;
    vertices = new HashMap();
    Vertex node;
    LSA lsa;
    for (Enumeration enum = lsas.elements(); enum.hasMoreElements();) {
      lsa = (LSA)enum.nextElement();
      node = new Vertex(lsa);
      vertices.put(node.getKey(), node);
    }
  }

  // ---------------------------  Dijkstra.firstStage --------------------------- //
  /** Compute the intra-area routes by building the shortest path tree for the area
   *  this Dijkstra belongs to. All routing table entries whose destination type is 
   *  "area border router" or "AS boundary router" are calculated here.
   *  @return A HashMap holding all new calculated area border and AS boundary router
   *          entries for the area this Dijkstra belongs to.
   */
  public HashMap firstStage() {
    Vector linkInfos;
    LinkInfo nextInfo;
    String key; // key of a vertex
    Vertex v; // adjacent vertex v
    LinkInfo vNextInfo; // a link info of the LSA of vertex v
    // a boolean value indicating whether the adjacent vertex v has an open link (link in state
    // FULL) back to the vertex justAdded.
    boolean isBidirectional = false;
    int dCost; // the cost of the resulting path from root to adjacent vertex v.
    NextHop nHop;
    // HashMap for routes to area border router. Key = router ID, value = RouterEntry.
    HashMap routerRoutes;

    // (1) Initialize the algorithm's data structures
    candidates = new HashMap();
    spTree = new HashMap();
    routerRoutes = new HashMap();

    justAdded = (Vertex)vertices.get(myOSPF.rtrid + " 0");
    justAdded.predecessors.add(justAdded);
    justAdded.dist = 0;
    root = justAdded;
    candidates.put(root.getKey(), root);

    isTransitCapable = false;

    // (2) Begin shortest path tree calculation.
    do {
      // RFC 2328 chapter 16.1 (3)
      justAdded = extractMin();
      spTree.put(justAdded.getKey(), justAdded);
      // RFC 2328 chapter 16.1 (2)
      if (justAdded.type == Vertex.ROUTER) {
        Router_LSA body = (Router_LSA)justAdded.myLSA.payload();
        if (body.isAreaBorderRouter || body.isASBoundaryRouter) {
          // Node is an area border or AS boundary router. Generate a RouterEntry.
          Vector sPaths = new Vector();
          ShortestPath newSP;
          RouterEntry newRoutEntry;
	  for (Enumeration e = justAdded.nextHops.elements(); e.hasMoreElements(); ) {
	    newSP = new ShortestPath((NextHop)e.nextElement());
            sPaths.add(newSP); 
	  }
          newRoutEntry = new RouterEntry(justAdded.myLSA.options.clone(), OSPF.INTRA_AREA,
                                         justAdded.dist, null, body.isASBoundaryRouter, sPaths);
          routerRoutes.put(new Integer(justAdded.id), newRoutEntry);
        }
        linkInfos = body.links;
        isTransitCapable = body.isVirtLinkEndPoint;
        for (Enumeration enum = linkInfos.elements(); enum.hasMoreElements(); ) {
          nextInfo = (LinkInfo)enum.nextElement();
          // RFC 2328 chapter 16.1 (2)(a)
          if (nextInfo.linkType == myOSPF.TO_STUB_NET) continue;
          key = (new Integer(nextInfo.linkID)).toString()+" "+(new Byte(Vertex.ROUTER)).toString();
          // RFC 2328 chapter 16.1 (2)(b)
          if (!vertices.containsKey(key)) continue; // LSA does not exist.
          v = (Vertex)vertices.get(key);
          if (v.myLSA.lsAge == myOSPF.MAX_AGE) continue; // LSA age is equal to MAX_AGE
          for (Enumeration vLinks = ((Router_LSA)v.myLSA.payload()).links.elements();
               vLinks.hasMoreElements(); ) {
	    vNextInfo = (LinkInfo)vLinks.nextElement();
            if ((justAdded.id == vNextInfo.linkID) && (vNextInfo.linkType != myOSPF.TO_STUB_NET)) {
	      isBidirectional = true;
              break;
            }
          }
          if (!isBidirectional) continue; // LSA has no appropriate link back.
          isBidirectional = false;
          // RFC 2328 chapter 16.1 (2)(c)
          if (spTree.containsKey(key)) continue;
          // RFC 2328 chapter 16.1 (2)(d)
          dCost = justAdded.dist + nextInfo.metric;
          if (candidates.containsKey(key)) {
	    int vCost = ((Vertex)candidates.get(key)).dist; // dist value of vertex v.
	    if (dCost > vCost) continue;
            if (dCost < vCost) {
	      v.dist = dCost;
              v.predecessors.clear(); // clear all previously added predecessors.
	      v.nextHops.clear(); // clear all previously added next hops.
            }
            if (!v.predecessors.contains(justAdded)) v.predecessors.add(justAdded);
	    // calculate the set of next hops and add it to v.
	    if (justAdded.equals(root)) {
	      // there may be only one new next hop, the one which was just found.
              // SSFnet supports ptp only, so no interface type must be tested!
              // Just add a next hop with viaInterface set only.
              nHop = new NextHop(nextInfo.linkData);
              if (!v.nextHops.contains(nHop)) v.nextHops.add(nHop);
            } else {
	      // inherit the next hops of the new predecessor.
              for (Enumeration hops = justAdded.nextHops.elements(); hops.hasMoreElements(); ) {
		nHop = (NextHop)hops.nextElement();
                if (!v.nextHops.contains(nHop)) v.nextHops.add(nHop);
              }
            }
          } else {
	    // adjust a few values of the new node v and finally add it to the candidates list.
	    v.dist = dCost;
            v.predecessors.add(justAdded);
            // calculate the set of next hops and SET it to v.
            v.nextHops.clear(); // clear all previously added next hops.
            if (justAdded.equals(root)) {
              // SSFnet supports ptp only, so no interface type must be tested!
              // Just add a next hop with viaInterface set only.
	      v.nextHops.add(new NextHop(nextInfo.linkData));
            } else {
              for (Enumeration hops = justAdded.nextHops.elements(); hops.hasMoreElements(); ) {
		nHop = ((NextHop)hops.nextElement());
                if (!v.nextHops.contains(nHop)) v.nextHops.add(nHop);
              }
            }
	    candidates.put(key, v);
          }
        }
      } else {
	// SSF-Net does not support broadcast! Network-nodes can not appear.
      }
    } while (!candidates.isEmpty());
    return routerRoutes; // Return HashMap with all area border routes.
  }

  // ---------------------------  Dijkstra.secondStage --------------------------- //
  /** Compute the intra-area routes to all networks within the area this Dijkstra belongs to.
   *  @return A HashMap holding all network entries for the area this Dijkstra belongs to.
   */
  public HashMap secondStage() {
    Vertex nextNode;
    LinkInfo nextLink;
    String key;
    HashMap stubNets = new HashMap();
    NetworkEntry netEntry;
    Vector sPaths; // A Vector holding new calculated ShortestPath objects.
    boolean hasEqualCost = false;
    for (Iterator nodes = spTree.values().iterator(); nodes.hasNext(); ) {
      nextNode = (Vertex)nodes.next();
      if (nextNode.type == Vertex.ROUTER) {
	for (Enumeration linkInfos = ((Router_LSA)nextNode.myLSA.payload()).links.elements();
             linkInfos.hasMoreElements(); ) {
	  nextLink = (LinkInfo)linkInfos.nextElement();
          if (nextLink.linkType == OSPF.TO_STUB_NET) {
	    // A Type 3 link (stub network). The current version of OSPFv2 knows ptp connected NON
	    // host routes only!! This makes it easy to generate a network entry. If host routes
	    // and broadcast or non broadcast (ptm and nbma) media will be supported in future the 
	    // following code must be adapted accordingly!!!
	    if (myArea.hasInterface(new Integer(nextLink.linkID))) {
	      // link is Loopback Interface or ptm! Not yet implemented!!!
	      continue; // ingnore this case.
            } else {
	      // link is a stub link according to RFC 2328 12.4.1.1. option 2
	      key = nextLink.linkID + "/" + nextLink.linkData; // generate destination key
              if (stubNets.containsKey(key)) {
                // there is already an entry for the "new" destination.
		int oldCost = ((NetworkEntry)stubNets.get(key)).cost;
	        int newCost = nextNode.dist + nextLink.metric;
                // Check whether the old entry is cheaper.
		if (oldCost < newCost) continue; // reject the current stub network link!
                if (oldCost == newCost) hasEqualCost = true; // adjust next hops only!
              }
              // Anyway, create here a Vector of new ShortestPath objects.
              sPaths = new Vector();
              if (nextNode.equals(root)) {
                // the root node itself has no nextHop for any stub network, so compute a ShortestPath.
	        int viaIntfIPAddr = nextLink.linkID + 1;
                if (!myArea.hasInterface(new Integer(viaIntfIPAddr))) viaIntfIPAddr++;
                sPaths.add(new ShortestPath(new NextHop(viaIntfIPAddr)));
              } else {
                // currently examined node is not a root node. No next hops to calculate, just
	        // set sPaths to the next hops calculated in firstStage().
		for (Enumeration e = nextNode.nextHops.elements(); e.hasMoreElements(); ) {
	          sPaths.add(new ShortestPath((NextHop)e.nextElement()));
                }
              }
              // Now adjust the entry found in stubNets or create a new one and add it to stubNets.
              if (hasEqualCost) {
		// add the next hops just found to the next hops of the current entry.
		ShortestPath sp;
		netEntry = (NetworkEntry)stubNets.get(key);
                for (Enumeration e = sPaths.elements(); e.hasMoreElements(); ) {
		  sp = (ShortestPath)e.nextElement();
		  if (!netEntry.equalCostPaths.contains(sp)) netEntry.equalCostPaths.add(sp);
                }
	        hasEqualCost = false;
              } else {
		// create a new NetworkEntry and put it in stubNets.
                netEntry = new NetworkEntry(myArea.areaID, OSPF.INTRA_AREA,
                           nextNode.dist + nextLink.metric, 0, null, sPaths);
                stubNets.put(key, netEntry);
              }
            }
          } 
        }
      } else {
        // SSF-Net does not support broadcast! Network-nodes can not appear.
      }
    }
    return stubNets;
  }

  // -------------------------- Dijkstra.extractMin ------------------------ //
  /**
   * Extract the node that has the minimum distance from the root.  If there
   * are ties, take the one with the smallest id.
   */
  private Vertex extractMin() {
    if (candidates.size() == 0) {
      return null;
    }
    Iterator candList = candidates.values().iterator();
    Vertex minVertex = (Vertex)candList.next();
    Vertex v;
    while (candList.hasNext()) {
      v = (Vertex)candList.next();
      if ((v.dist < minVertex.dist) || (v.dist == minVertex.dist && v.id < minVertex.id))
        minVertex = v;
    }
    return (Vertex)candidates.remove(minVertex.getKey());
  }

  // -------------------------- Dijkstra.getSPTree --------------------------------- //
  /**
   *  Return the current shortest path tree.
   *  @return HashMap representing the shortest path tree in form of String-Vertex mappings.
   */
  public HashMap getSPTree() {
    return spTree;
  }


  // ============================== inner class Vertex ============================= //
  /**
   * A node corresponding to a vertex in a graph upon which Dijkstra's
   * algorithm is being run.  It contains information about the vertex which is
   * used by the algorithm but which is not normally kept by the vertex itself.
   */
  class Vertex {

    // ................................ constants ................................. //

    /** a constant indicating that this is a router-vertex. */
    public static final byte ROUTER = 0;

    /** a constant indicating that this is a transit-network-vertex. */
    public static final byte NETWORK = 1;

    // ............................... member data ................................ //

    /** Together with the vertex type (router or network) this id uniquely
     *  identifies the vertex.
     *  router vertex: id = router's OSPF Router ID.
     *  network vertex: id = IP address of the network's Designated Router.
     */
    int id;

    /** A byte value indicating the type of this vertex. */
    byte type;

    /** Associated LSA.
     *  router vertex: myLSA = Router_LSA
     *  network vertex: myLSA = Network_LSA
     */
    LSA myLSA;

    /** A Vector referencing to the Vextices which are predecessors of this vertex. */
    Vector predecessors;

    /** The shortest-path estimate from the root to this vertex. */
    int dist;

    /** A Vector of NextHop Objects for the current set of shortest paths from the root
     *  to this vertex. Each NextHop indicates the outgoing router interface to
     *  use, when forwarding traffic to the destination, and if exists the ip address
     *  of the next hop router. In case of POINT-TO-POINT links it contains only Integers
     *  indicating the forwarding interface.
     */
    Vector nextHops;

    public Vertex(LSA assocLSA) {
      if (assocLSA.lsType == LSA.ROUTER_LSA) {
        id   = assocLSA.advRouter;
        type = ROUTER;
      } else if (assocLSA.lsType == LSA.NETWORK_LSA) {
	// id = IP address of network's DR.
        type = NETWORK;
      }
      myLSA        = assocLSA;
      predecessors = new Vector();
      dist         = Integer.MAX_VALUE;
      nextHops     = new Vector();
    }

    // ------------------------------ Vertex.getKey ------------------------------------ //
    /** Return a key which uniquely identifies this vertex. The key is a String holding
     *  id and type separated by a whitespace.
     */
    public String getKey() {
      return (id + " " + type);
    }

    // ------------------------------ Vertex.equals ------------------------------------ //
    /** Indicates whether a Vertex object is "equal" to this one.
     *  @param vertexObj Vertex object to compare.
     *  @return boolean value indicating true if the Objects are equal else indicating false.
     */
    @Override
	public boolean equals(Object vertexObj) {
      if (!(vertexObj instanceof Vertex)) return false;
      Vertex vt = (Vertex)vertexObj;
      if (!(getKey().equals(vt.getKey()))) return false;
      return true;
    }

  } // end inner class Vertex


} // end class Dijkstra
